package leetCode;

public class T28M2 {
    public static void main(String[] args) {
        System.out.println(new SolutionT28M2().strStr("mississippi",
                "issip"));
    }

}

class SolutionT28M2 {
    public int strStr(String haystack, String needle) {
        int[] next = next(needle);
        int j=0;
        char[] charsHaystack = haystack.toCharArray();
        char[] charsNeedle = needle.toCharArray();
        for (int i=0;i<haystack.length();i++){
            if (charsNeedle[j]!=charsHaystack[i]){
                if (j>0){
                    j=next[j-1];
                }

            }
            j++;
            if (j==needle.length()-1){
                return i-needle.length()+1;
            }
        }
        return -1;
    }
    public int[]next(String needle){
        int[]next=new int[needle.length()];
        char[] charArrayChars = needle.toCharArray();
        int j=0;
        next[0]=0;
        for (int i=1;i<needle.length();i++){
            while (j>0&&charArrayChars[i]!=charArrayChars[j]){
                j=next[j-1];
            }
            if (charArrayChars[i]==charArrayChars[j]){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}